K-nearest neighbor

KNN(K-최근접 이웃, K-Nearest Neighbor)은 직관적이고 간단한 방법에 비해 좋은 성능을 보여주어 종종 사용되는 머신러닝 알고리즘이다. 대부분의 머신러닝 알고리즘은 훈련데이터를 통해 모델을 생성하는 방식이라면, KNN은 하나하나의 데이터 값을 통해 학습을 시행하고 따로 모델을 생성하지 않는 비모수 방식이라는 특징이 있다. KNN 알고리즘의 작동방식에 대해 알아보기전 KNN의 특징인 비모수 방식에 대해 짚고 넘어가보자.

모수 방식과 비모수 방식의 가장 큰 차이는 확률분포의 개념을 활용하느냐의 차이이다. 예를 들어, 모수 방식인 선형 회귀는 두 변수 사이의 관계를 표현하는 것인데 이때 생기는 오차는 정규분포, 즉 확률분포로 정규분포를 따르기 때문에 확률분포의 개념을 활용한다. 반대로 비모수 방식은 두 변수 사이의 관계를 표현할때 생기는 오차는 정규분포를 따르지 않는다고 할 수 있다. 즉, 비모수 방식은 오차가 특정 분포를 이루고 있는게 아니라 의미없이 오차들이 골고루 분포하고 있는 것이기 때문에 확률분포의 개념을 활용하지 않는 것이다.

모수 방식과 비모수 방식은 선형, 비선형과 관련있다.
모수 방식은 변수가 선형 관계일때 활용하고, 비모수 방식은 변수가 비선형 관계일때 활용하는 것이 적합한 방식이다.

KNN은 대표적인 비모수 방식으로 데이터 간의 거리를 활용해 알고리즘이 작동한다. 만약 임의로 지정한 k=3이라면 (일반적으로 k는 홀수를 사용, 짝수의 k는 동점을 초래하기 때문) 새로 들어온 데이터에서 거리가 가까운 3개의 데이터를 통해 분류를 시행한다. 모델을 별도로 생성하지 않는 알고리즘의 특성상 결정 경계(Decision Boundary)가 존재하지 않으며, 새로운 데이터가 주어지면 학습을 통해 새로 모델을 생성할 필요없이 새로운 데이터만 추가하여 분류한다. 그리고 거리를 기반으로 분류하여 이상치, 노이즈에 크게 영향을 받지 않는다는 장점도 있다.

KNN은 유클리드 거리와 마할라노비스 거리 등 다양한 계산방식을 통해 거리 측정이 가능하다. 유클리드 거리는 흔히 알고있는 피타고라스 정리에 기초해서 거리를 구하는 방식이고, 마할라노비스 거리는 각 특성의 분포를 파악하고 실제로 같은 거리라도 특성마다 다르게 측정하는 방식이다. 거리를 측정하기 위한 특성으로 x, y가 있다고 가정해보자. 특성 x의 분산이 특성 y보다 크다면 x의 분포가 더욱 퍼져있을것이고, 이때 분산을 거리의 기준으로 보면 특성 x에서의 거리는 동일한 거리라도 특성 y에서 보다 더 짧다고 볼 수 있다. 이처럼 특성마다 분포가 다르기 때문에 거리의 스케일이 다를것이고 이를 동일하게 하기 위해 마할라노비스 거리를 활용한다.

차원의 저주 : 유클리드 거리가 고차원에서 도움이 되지 않음, 차원의 증가로 인한 데이터 간 거리 증가, PCA활용

결론

• KNN은 특정한 모델을 생성하지 않고 데이터를 통해 학습을 시행하는 비모수 방식이다.
• 거리를 기반 알고리즘이기 때문에 노이즈에 크게 영향을 받지 않는다.
• 거리 측정을 위한 방법으로 크게 유클리드 거리와 마할라노비스 거리가 있다.